/*
归并排序是一种基于分治法的高效排序算法。它通过递归地将数组划分成两半，然后将每一半分别排序，最后合并成一个有序的数组。归并排序的时间复杂度是 
𝑂(𝑛log𝑛)
O(nlogn)，空间复杂度是 𝑂(𝑛)
*/



/*
代码解读
merge：合并两个有序数组的函数，将两个有序子数组合并成一个有序数组。
mergeSort：递归的归并排序函数，按照分治法将数组划分，然后递归地排序每一半，最后合并成一个有序数组。
主程序：测试归并排序，通过调用 mergeSort 对数组进行排序，并输出排序前后的结果。
归并排序的特点
稳定性：归并排序是稳定的，即相同的元素在排序后保持原始顺序。
适用性：归并排序适用于大型数据集，因为时间复杂度较低，而且分治法的递归结构适合并行化处理。
空间消耗：归并排序需要额外的空间来存储临时数组，空间复杂度为 
𝑂(𝑛)。
归并排序是一个重要的排序算法，广泛用于需要稳定排序且数据量大的场合，例如外部排序和并行计算。


*/


#include <stdio.h>
#include <stdlib.h>

// 合并两个有序数组的函数
void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;  // 左子数组长度
    int n2 = right - mid;  // 右子数组长度

    // 创建临时数组
    int* leftArr = (int*)malloc(n1 * sizeof(int));
    int* rightArr = (int*)malloc(n2 * sizeof(int));

    // 复制数据到临时数组
    for (int i = 0; i < n1; i++) {
        leftArr[i] = arr[left + i];
    }
    for (int j = 0; j < n2; j++) {
        rightArr[j] = arr[mid + 1 + j];
    }

    int i = 0, j = 0, k = left;

    // 合并临时数组
    while (i < n1 && j < n2) {
        if (leftArr[i] <= rightArr[j]) {
            arr[k] = leftArr[i];
            i++;
        } else {
            arr[k] = rightArr[j];
            j++;
        }
        k++;
    }

    // 将左子数组的剩余部分复制到arr
    while (i < n1) {
        arr[k] = leftArr[i];
        i++;
        k++;
    }

    // 将右子数组的剩余部分复制到arr
    while (j < n2) {
        arr[k] = rightArr[j];
        j++;
        k++;
    }

    free(leftArr);  // 释放临时数组
    free(rightArr);
}

// 归并排序的递归函数
void mergeSort(int arr[], int left, int right) {
    if (left < right) {  // 如果区间长度大于1
        int mid = left + (right - left) / 2;  // 计算中间索引

        // 递归对左半部分排序
        mergeSort(arr, left, mid);

        // 递归对右半部分排序
        mergeSort(arr, mid + 1, right);

        // 合并两部分
        merge(arr, left, mid, right);
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int size = sizeof(arr) / sizeof(arr[0]);

    printf("原始数组: ");
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    // 归并排序
    mergeSort(arr, 0, size - 1);

    printf("排序后数组: ");
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}
